Introduction - REMitW
サマリー
RE2というオープンソースの正規表現実装と、その背景理論について解説する
背景理論は前の2記事で紹介したDFAとNFA
線形時間実行と、スタックの深さが固定されるのが特徴
PCRE
を使うとバックトラッキングアルゴリズムを使うので、Dos攻撃対象になる
Google
Code Search
,
Sawzall
,
Bigtable
で利用されている
用語
決定性有限オートマトン(DFA)
非決定性有限オートマトン(NFA)
Code Search
PCRE(Perl互換正規表現)
RE2
DoS(サービス拒否)攻撃